Как мы математически описываем невидимые нити, соединяющие общество? Будь то Числа Бейкона связывающие Белу Лугоси с голливудскими знаменитостями или Графы подобия кластеризация точек данных на основе близости, Теория графов предоставляет формальный язык $G = (V, E)$ для моделирования этих дискретных вселенных.
1. Анатомия графов
В основе своей граф состоит из множества вершин ($V$) и множества ребер ($E$). Однако правила поведения варьируются в зависимости от структуры:
- Простой граф: Наиболее элегантная форма; она запрещает циклы (ребра, соединяющие вершину с самой собой) и параллельные ребра (избыточные ребра между одними и теми же двумя точками).
- Мультиграф: Разрешает циклы и параллельные ребра, часто используется для моделирования различных типов взаимодействий (например, текстовые сообщения против звонков) между одними и теми же двумя узлами.
- Изолированная вершина: Вершина $v$ является изолированной, если к ней не присоединено ни одно ребро, что представляет объект без отношений в текущем наборе.
В области науки о данных мы часто используем Функцию несходства для построения графов:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Мы проводим ребро между $v$ и $w$, только если $s(v, w)$ ниже определенного порога, эффективно создавая сеть «соседей».
2. Пути, связность и компоненты
Путь — это последовательность вершин и ребер. Если путь не посещает никакую вершину более одного раза, он называется простым путем. Связность — это сердце графа: простым путем. Связность — это сердце графа:Связный граф: существует путь между каждыми двумя вершинами графа.
- Связный граф: Существует путь между каждой парой вершин в графе.
- Компоненты: Если граф несвязен, он распадается на непересекающиеся части, называемые компонентами. Каждая компонента — это максимальный связный подграф.
3. Подграфы: Архитектура подмножеств
Подграф $G' = (V', E')$ — это подмножество графа $G$, такое что каждая вершина из $V'$ существует в $V$, а каждое ребро из $E'$ соединяет вершины, найденные в $V'$. Выявление подграфов критически важно для обнаружения локальных паттернов внутри глобальных сетей.